/**
 * @a https://leetcode.cn/problems/longest-valid-parentheses/description/
 */


#include "common.h"


class Solution {
public:
    int longestValidParentheses(string s) {
        int sz = s.size();
        vector<int> dp(sz,0);
        int maxlen = 0;
        for(int i = 1; i < sz; ++i){
            if(s[i] == ')')
            {
                if(s[i - 1] == '(')
                {
                    dp[i] = 2;
                    if(i - 2 >= 0)
                        dp[i] += dp[i-2];
                }
                else if(dp[i - 1] > 0)
                {
                    if((i - dp[i - 1] - 1) >= 0 && s[i - dp[i - 1] - 1] == '(')
                    {
                        dp[i] = dp[i - 1] + 2;
                        if((i - dp[i - 1] - 2) >= 0)
                            dp[i] = dp[i] + dp[i - dp[i - 1] - 2];
                    }
                }
            }
            maxlen = maxlen > dp[i] ? maxlen : dp[i];
        }
        return maxlen;
    }
};